/* Time-stamp: <2010-09-21 00:09:19 xinhaoyuan> */
/* This code is implemented by Xinhao.Yuan for research propose */

#include "flash.h"
#include "sftl.h"
#include "type.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int sftl_oldest_dir;
int sftl_newest_dir;

#define USE_BITMAP 1
#define USE_COMPACT 1
#define COMPACT_BITMAP 1

struct sftl_dir_entry *sftl_dir;
unsigned char *sftl_valid_bitmap;
unsigned char *sftl_blk_valid_count;
int *sftl_blk_vc_idx;
int *sftl_blk_vc_heap;
int *sftl_inverse_map;

unsigned int sftl_pages_count;
unsigned int sftl_blk_count;
unsigned int sftl_dir_count;

unsigned int sftl_free_blk;
unsigned int sftl_free_count;
unsigned int sftl_free_arr[PAGE_NUM_PER_BLK];

unsigned int sftl_compact_dir_count;
unsigned int sftl_total_compact_count;
unsigned int sftl_total_flat_count;
unsigned int sftl_total_limit;

unsigned int sftl_stat_replace_out;
unsigned int map_write_count = 0;

unsigned int sftl_stat_access_count = 0;
unsigned int sftl_stat_hit_count = 0;

unsigned int sftl_switch_merge_count;
unsigned int sftl_partial_merge_count;

unsigned int sftl_gc_count;
unsigned int sftl_operation_count;

const char *sftl_log_filename = "sftl.log";
FILE *sftl_log_file;

#define SFTL_LEVEL_MAX 100
int sftl_stat_bucket_curr;
int sftl_stat_bucket_level[SFTL_LEVEL_MAX];
double sftl_stat_bucket_value[SFTL_LEVEL_MAX];

void sftl_stat_bucket_push(double v)
{
	 sftl_stat_bucket_level[sftl_stat_bucket_curr] = 1;
	 sftl_stat_bucket_value[sftl_stat_bucket_curr] = v;
	 while (sftl_stat_bucket_curr > 0 &&
			sftl_stat_bucket_level[sftl_stat_bucket_curr - 1] ==
			sftl_stat_bucket_level[sftl_stat_bucket_curr])
	 {
		  ++ sftl_stat_bucket_level[sftl_stat_bucket_curr - 1];
		  sftl_stat_bucket_value[sftl_stat_bucket_curr - 1] +=
			   sftl_stat_bucket_value[sftl_stat_bucket_curr];
		  -- sftl_stat_bucket_curr;
	 }

	 ++ sftl_stat_bucket_curr;
}

double sftl_stat_bucket_clean()
{
	 int i;
	 double result = 0;
	 for (i = sftl_stat_bucket_curr - 1; i >= 0 ; -- i)
	 {
		  result += sftl_stat_bucket_value[i];
	 }
	 sftl_stat_bucket_curr = 0;
	 return result;
}

int sftl_get_valid_bitmap(int page)
{
	 if ((sftl_valid_bitmap[page >> 3] & (1 << (page & 7))) == 0)
		  return 0;
	 else return 1;
}

void sftl_set_valid_bitmap(int page, int valid)
{
	 int blk = page / PAGE_NUM_PER_BLK;
	 if (valid == 0)
	 {
		  if ((sftl_valid_bitmap[page >> 3] & (1 << (page & 7))) != 0)
		  {
			   // fprintf(stderr, " - valid count for %d\n", blk);
			   -- sftl_blk_valid_count[blk];
			   
			   int cur = sftl_blk_vc_heap[blk];
			   while (cur > 1)
			   {
					if (sftl_blk_valid_count[blk] <
						sftl_blk_valid_count[sftl_blk_vc_idx[cur >> 1]])
					{
						 sftl_blk_vc_idx[cur] = sftl_blk_vc_idx[cur >> 1];
						 sftl_blk_vc_heap[sftl_blk_vc_idx[cur]] = cur;
						 cur = cur >> 1;
					}
					else break;
			   }
			   sftl_blk_vc_idx[cur] = blk;
			   sftl_blk_vc_heap[blk] = cur;
		  }
		  sftl_valid_bitmap[page >> 3] &= ~(1 << (page & 7));
	 }
	 else
	 {
		  if ((sftl_valid_bitmap[page >> 3] & (1 << (page & 7))) == 0)
		  {
			   // fprintf(stderr, " + valid count for %d\n", blk);
			   ++ sftl_blk_valid_count[blk];

			   int cur = sftl_blk_vc_heap[blk];
			   while (1)
			   {
					int victim = cur << 1;
					if (victim > sftl_blk_count) break;
					if (victim + 1 <= sftl_blk_count &&
						sftl_blk_valid_count[sftl_blk_vc_idx[victim]] >
						sftl_blk_valid_count[sftl_blk_vc_idx[victim + 1]])
						 ++ victim;
					
					if (sftl_blk_valid_count[blk] >
						sftl_blk_valid_count[sftl_blk_vc_idx[victim]])
					{
						 sftl_blk_vc_idx[cur] = sftl_blk_vc_idx[victim];
						 sftl_blk_vc_heap[sftl_blk_vc_idx[cur]] = cur;
						 cur = victim;
					}
					else break;
			   }
			   sftl_blk_vc_idx[cur] = blk;
			   sftl_blk_vc_heap[blk] = cur;
		  }
		  sftl_valid_bitmap[page >> 3] |= (1 << (page & 7));
	 }
}

unsigned int sftl_get_free(int mapdir_flag);
void sftl_gc(int blkno, int mapdir_flag);

/* ============================================================ */

void sftl_stat_reset()
{
	 sftl_stat_access_count = 0;
	 sftl_stat_hit_count = 0;
	 
	 sftl_stat_replace_out = 0;
	 map_write_count = 0;
	 
	 sftl_switch_merge_count = 0;
	 sftl_partial_merge_count = 0;

	 sftl_gc_count = 0;
	 sftl_operation_count = 0;
	 
	 sftl_stat_bucket_clean();

	 fclose(sftl_log_file);
	 sftl_log_file = fopen("sftl.log", "w");
}

int sftl_init(blk_t blk_num, blk_t extra_num)
{
	 fprintf(stderr, "sftl initialized with blk_num = %d, extra_num = %d\n",
			 blk_num, extra_num);

	 sftl_pages_count = blk_num * PAGE_NUM_PER_BLK;
	 sftl_blk_count = blk_num;
	 sftl_dir_count = sftl_pages_count / MAP_ENTRIES_PER_PAGE;

	 fprintf(stderr, "pages_count = %d, dir_count = %d\n", sftl_pages_count, sftl_dir_count);
	 fprintf(stderr, "limit = %d\n", SFTL_TOTAL_LIMIT);

	 sftl_dir = (struct sftl_dir_entry *)malloc(sizeof(struct sftl_dir_entry) * sftl_dir_count);
	 int i;
	 for (i = 0; i != sftl_dir_count; ++ i)
	 {
		  sftl_dir[i].type = SFTL_MF_INVALID;
	 }

	 sftl_compact_dir_count = 0;
	 sftl_total_compact_count = 0;
	 sftl_total_flat_count = 0;

	 /* 4MB space for running sftl */
	 sftl_total_limit = SFTL_TOTAL_LIMIT;

	 sftl_valid_bitmap = (unsigned char *)malloc((sftl_pages_count + 7) / 8);
	 sftl_blk_valid_count = (unsigned char *)malloc(sftl_blk_count);
	 sftl_blk_vc_heap = (int *)malloc(sftl_blk_count * sizeof(int));
	 sftl_blk_vc_idx = (int *)malloc((sftl_blk_count + 1) * sizeof(int));
	 memset(sftl_valid_bitmap, 0, (sftl_pages_count + 7) / 8);
	 memset(sftl_blk_valid_count, 0, sftl_blk_count);
	 for (i = 0; i != sftl_blk_count; ++i)
	 {
		  sftl_blk_vc_heap[i] = i + 1;
		  sftl_blk_vc_idx[i + 1] = i;
	 }

#if USE_BITMAP
	 sftl_free_blk = -1;
	 sftl_free_count = 0;
#else
	 nand_blk[0].state.free = 0;
	 nand_erase(0);
	 nand_blk[0].state.free = 0;
	 
	 sftl_free_blk = 0;
	 sftl_free_count = PAGE_NUM_PER_BLK -1;
	 for (i = 0; i != sftl_free_count; ++ i)
	 {
		  sftl_free_arr[i] = i;
	 }
#endif

	 sftl_oldest_dir = sftl_newest_dir = -1;
	 sftl_stat_replace_out = 0;

	 sftl_inverse_map = (int *)malloc(sftl_blk_count * PAGE_NUM_PER_BLK * sizeof(int));
	 memset(sftl_inverse_map, -1, sftl_blk_count * PAGE_NUM_PER_BLK * sizeof(int));

	 sftl_switch_merge_count = 0;
	 sftl_partial_merge_count = 0;

	 sftl_log_file = fopen(sftl_log_filename, "w");

	 sftl_gc_count = 0;
	 sftl_operation_count = 0;

	 sftl_stat_access_count = 0;
	 sftl_stat_hit_count = 0;

	 sftl_stat_bucket_curr = 0;

	 return 0;
}

size_t sftl_read(sect_t lsn, sect_t size, int mapdir_flag)
{
	 if ((!USE_COMPACT) && sftl_total_compact_count > 0)
	 {
		  fprintf(stderr, "error existing compact\n");
		  assert(0);
	 }
	 
#ifdef SFTL_DEBUG
	 fprintf(stderr, "sftl::read called with lsn = %d, size = %d, mapdir_flag = %d\n",
			 lsn, size, mapdir_flag);
#endif
	 
	 int i;
	 int lpn = lsn / SECT_NUM_PER_PAGE; // logical page number
	 int ldn = lpn / MAP_ENTRIES_PER_PAGE;
	 
	 int size_page = size/SECT_NUM_PER_PAGE; // size in page 
	 int sect_num;
	 
	 sect_t s_lsn;	// starting logical sector number
	 sect_t s_psn; // starting physical sector number 
	 
	 sect_t lsns[SECT_NUM_PER_PAGE];
	 
	 ASSERT(lpn < sftl_pages_count);
	 ASSERT(lpn + size_page <= sftl_pages_count);
	 
	 memset (lsns, 0xFF, sizeof (lsns));
	 
	 sect_num = (size < SECT_NUM_PER_PAGE) ? size : SECT_NUM_PER_PAGE;
	 
	 if(mapdir_flag == 2)
	 {
		  s_lsn = ldn * MAP_ENTRIES_PER_PAGE * SECT_NUM_PER_PAGE;
		  
		  /* Read mapping from disk */
		  s_psn = sftl_dir[ldn].mapping_ppn * SECT_NUM_PER_PAGE;
		  sftl_dir[ldn].compact_size = 0;
		  for (i = 1; i != MAP_ENTRIES_PER_PAGE; ++i)
		  {
			   if (sftl_dir[ldn].ppn[i - 1] + 1 != sftl_dir[ldn].ppn[i])
			   {
					++ sftl_dir[ldn].compact_size;
			   }
		  }

		  /* Threshold */
		  if (sftl_dir[ldn].compact_size * 5 < MAP_ENTRIES_PER_PAGE * 4 && USE_COMPACT)
		  {
			   sftl_dir[ldn].type = SFTL_MF_COMPACT;
			   sftl_compact_dir_count += 1;
			   sftl_total_compact_count += sftl_dir[ldn].compact_size;
		  }
		  else
		  {
			   sftl_dir[ldn].type = SFTL_MF_FLAT;
			   sftl_total_flat_count += MAP_ENTRIES_PER_PAGE;
		  }

		  sftl_dir[ldn].dirty = 0;
	 }
	 else if (sftl_dir[ldn].type == SFTL_MF_COMPACT ||
			  sftl_dir[ldn].type == SFTL_MF_FLAT)
	 {
		  s_lsn = lpn * SECT_NUM_PER_PAGE;
		  
		  unsigned int ppn = sftl_dir[ldn].ppn[lpn % MAP_ENTRIES_PER_PAGE];
		  if (ppn == -1) return 0;
		  
		  s_psn = ppn * SECT_NUM_PER_PAGE;
	 }
	 else
	 {
		  fprintf(stderr, "ERROR, page map should in SRAM\n");
	 }
	 
	 for (i = 0; i < SECT_NUM_PER_PAGE; i++) {
		  lsns[i] = s_lsn + i;
	 }
	 
	 if(mapdir_flag == 2){
		  // map_pg_read++;
	 }
	 
	 size = nand_page_read(s_psn, lsns, 0);
	 ASSERT(size == SECT_NUM_PER_PAGE);
	 
	 return sect_num;
}

size_t sftl_write(sect_t lsn, sect_t size, int mapdir_flag)
{
	 if ((!USE_COMPACT) && sftl_total_compact_count > 0)
	 {
		  fprintf(stderr, "error existing compact\n");
		  assert(0);
	 }
	 
#ifdef SFTL_DEBUG
	 fprintf(stderr, "sftl::write called with lsn = %d, size = %d, mapdir_flag = %d\n",
			 lsn, size, mapdir_flag);
#endif
	 
	 int i;
	 int lpn = lsn / SECT_NUM_PER_PAGE; // logical page number
	 int ldn = lpn / MAP_ENTRIES_PER_PAGE;
	 
	 int size_page = size/SECT_NUM_PER_PAGE; // size in page 
	 int ppn;
	 int small;

	 sect_t lsns[SECT_NUM_PER_PAGE];
	 int sect_num = SECT_NUM_PER_PAGE;

	 sect_t s_lsn;	// starting logical sector number
	 sect_t s_psn; // starting physical sector number 
	 sect_t s_psn1;


	 ASSERT(lpn < sftl_pages_count);
	 ASSERT(lpn + size_page <= sftl_pages_count);

	 ppn = sftl_get_free(mapdir_flag);

	 memset (lsns, 0xFF, sizeof (lsns));
	 
	 if (mapdir_flag == 2) //map page
	 {
		  ++ map_write_count;
		  
		  s_lsn = ldn * MAP_ENTRIES_PER_PAGE * SECT_NUM_PER_PAGE;
		  
		  if (sftl_dir[ldn].mapping_ppn != -1 && sftl_dir[ldn].dirty == 0)
			   sftl_set_valid_bitmap(sftl_dir[ldn].mapping_ppn, 0);
		  sftl_dir[ldn].mapping_ppn = ppn;
		  sftl_inverse_map[ppn] = -ldn - 2;
	 }
	 else if (mapdir_flag == 1) //data page
	 {
		  s_lsn = lpn * SECT_NUM_PER_PAGE;
		  
		  int offset = lpn % MAP_ENTRIES_PER_PAGE;
		  int delta = 0;

		  if (sftl_dir[ldn].ppn[offset] != -1)
		  {
			   sftl_set_valid_bitmap(sftl_dir[ldn].ppn[offset], 0);
		  }

		  if (offset != 0)
		  {
			   if (sftl_dir[ldn].ppn[offset] - 1 == sftl_dir[ldn].ppn[offset - 1])
					++ delta;
			   if (ppn - 1 == sftl_dir[ldn].ppn[offset - 1])
					-- delta;
			   
			   // fprintf(stderr, "%d ", sftl_dir[ldn].ppn[offset - 1]);
		  }

		  // fprintf(stderr, "%d ==> %d", sftl_dir[ldn].ppn[offset], ppn);
		  
		  if (offset != MAP_ENTRIES_PER_PAGE -1)
		  {
			   if (sftl_dir[ldn].ppn[offset] + 1 == sftl_dir[ldn].ppn[offset + 1])
					++ delta;
			   if (ppn + 1 == sftl_dir[ldn].ppn[offset + 1])
					-- delta;

			   // fprintf(stderr, " %d", sftl_dir[ldn].ppn[offset + 1]);
		  }

		  // fprintf(stderr, "\n");

		  int new_compact_size;
#if COMPACT_BITMAP
		  new_compact_size = (MAP_ENTRIES_PER_PAGE + (sftl_dir[ldn].compact_size + delta) * 32 + 7) / 8;
#else
		  new_compact_size = (sftl_dir[ldn].compact_size + delta) * SFTL_COMPACT_SIZE;
#endif
		  
		  if (sftl_dir[ldn].type == SFTL_MF_COMPACT)
		  {
			   if (new_compact_size >
			   	   MAP_ENTRIES_PER_PAGE * SFTL_FLAT_SIZE)
			   {
					// fprintf(stderr, "SFTL::write mapdir %d changed into flat from\n", ldn);
					
			   		sftl_dir[ldn].type = SFTL_MF_FLAT;
					sftl_compact_dir_count -= 1;
			   		sftl_total_compact_count -= sftl_dir[ldn].compact_size;
			   		sftl_total_flat_count += MAP_ENTRIES_PER_PAGE;
			   }
			   else
			   {
					sftl_total_compact_count += delta;
			   }				   
		  }
		  else if (USE_COMPACT)
		  {
			   // fprintf(stderr, "SFTL:: mapdir %d compact size %d\n", ldn, sftl_dir[ldn].compact_size);
			   
			   if (new_compact_size <
			   	   MAP_ENTRIES_PER_PAGE * SFTL_FLAT_SIZE * 0.8)
			   {
					// fprintf(stderr, "SFTL::write mapdir %d changed into compact from\n", ldn);
					
			   		sftl_dir[ldn].type = SFTL_MF_COMPACT;
					sftl_compact_dir_count += 1;
			   		sftl_total_compact_count += sftl_dir[ldn].compact_size + delta;
			   		sftl_total_flat_count -= MAP_ENTRIES_PER_PAGE;
			   }
		  }


		  if (sftl_dir[ldn].mapping_ppn != -1 &&
			  sftl_dir[ldn].dirty == 0)
		  {
			   sftl_set_valid_bitmap(sftl_dir[ldn].mapping_ppn, 0);
		  }
		  sftl_dir[ldn].dirty = 1;
		  sftl_dir[ldn].compact_size += delta;
		  sftl_dir[ldn].ppn[offset] = ppn;
		  sftl_inverse_map[ppn] = lpn;
	 }
	 else{
		  fprintf(stderr, "something corrupted");
		  return 0;
	 }

	 for (i = 0; i < SECT_NUM_PER_PAGE; i++) 
	 {
		  lsns[i] = s_lsn + i;
	 }


	 s_psn = ppn * SECT_NUM_PER_PAGE;
	 nand_page_write(s_psn, lsns, 0, mapdir_flag);
	 sftl_set_valid_bitmap(ppn, 1);
	 return sect_num;
}

void sftl_end()
{
	 fprintf(sftl_log_file, "SFTL STAT: compact rate avg. %lf\n",
			 sftl_stat_bucket_clean() / sftl_stat_access_count);
	 fprintf(sftl_log_file, "SFTL STAT: access: %d, hit: %d\n",
			 sftl_stat_access_count, sftl_stat_hit_count);
	 fprintf(sftl_log_file, "SFTL STAT: replace out count: %d\n", sftl_stat_replace_out);
	 fprintf(sftl_log_file, "SFTL STAT: map write count: %d\n", map_write_count);
	 fprintf(sftl_log_file, "SFTL STAT: switch merge count: %d\n", sftl_switch_merge_count);
	 fprintf(sftl_log_file, "SFTL STAT: partial merge count: %d\n", sftl_partial_merge_count);
	 
	 free(sftl_dir);
	 free(sftl_valid_bitmap);
	 free(sftl_blk_valid_count);
	 free(sftl_blk_vc_idx);
	 free(sftl_blk_vc_heap);
	 free(sftl_inverse_map);

	 fclose(sftl_log_file);
}

/* ============================================================ */

int get_compact_size()
{
#if COMPACT_BITMAP
	 return (sftl_compact_dir_count * MAP_ENTRIES_PER_PAGE +
			 sftl_total_compact_count * 32 + 7) / 8;
#else
	 return sftl_total_compact_count * SFTL_COMPACT_SIZE;
#endif

}
int is_mapping_cache_full()
{
	 return get_compact_size() +
		  sftl_total_flat_count * SFTL_FLAT_SIZE >= sftl_total_limit;
}

void sftl_mapping_clean()
{
#ifdef SFTL_DEBUG
	 fprintf(stderr, "sftl::mapping_clean called\n");
#endif

	 /* fprintf(stderr, "compact_count = %d, flat_count = %d\n", */
	 /* 		 sftl_total_compact_count, sftl_total_flat_count); */
	 
	 while (is_mapping_cache_full())
	 {
#ifdef SFTL_DEBUG
		  fprintf(stderr, "  try to clean out a page dir mapping\n");
#endif		  
		  /* The SRAM is full, here we select a victim */
		  unsigned int victim_dir = sftl_oldest_dir;
		  if (sftl_dir[victim_dir].dirty == 1)
		  {
			   /* Write the mapping into disk */
			   send_flash_request(victim_dir * MAP_ENTRIES_PER_PAGE * SECT_NUM_PER_PAGE, 4, 0, 2);
			   ++ sftl_stat_replace_out;
		  }

		  if (sftl_dir[victim_dir].type == SFTL_MF_COMPACT)
		  {
			   sftl_compact_dir_count -= 1;
			   sftl_total_compact_count -= sftl_dir[victim_dir].compact_size;
		  }
		  else if (sftl_dir[victim_dir].type == SFTL_MF_FLAT)
		  {
			   sftl_total_flat_count -= MAP_ENTRIES_PER_PAGE;
		  }
		  else
		  {
			   fprintf(stderr, "sflt::mapping_clean: ERROR, dir = %d, type = %d\n", victim_dir, sftl_dir[victim_dir].type);
		  }

		  sftl_dir[victim_dir].type = SFTL_MF_DISK;
		  /* Update the victim */
		  sftl_oldest_dir = sftl_dir[victim_dir].newer;
		  if (sftl_oldest_dir != -1)
			   sftl_dir[sftl_oldest_dir].older = -1;
		  else sftl_newest_dir = -1;
	 }
}

unsigned int sftl_get_free(int mapdir_flag)
{
#ifdef SFTL_DEBUG
	 fprintf(stderr, "sftl::get_free called\n");
#endif

#if !USE_BITMAP
	 if (sftl_free_count == 0)
	 {
		  sect_t lsns[SECT_NUM_PER_PAGE];
		  int i;
		  for  (i = 0; i != SECT_NUM_PER_PAGE; ++ i)
		  {
			   lsns[i] = sftl_free_blk;
		  }
		  /* Write the inverse map */
		  nand_page_write(((sftl_free_blk + 1) * PAGE_NUM_PER_BLK - 1) * 4, lsns, 2, mapdir_flag);
	 }
#endif
	 
	 while (sftl_free_count == 0)
	 {
		  /* int i; */
		  /* for (i = 1; i <= 10; ++ i) */
		  /* 	   fprintf(stderr, " %d", sftl_blk_vc_idx[i]); */
		  /* fprintf(stderr, "\n"); */
		  sftl_free_blk = sftl_blk_vc_idx[1];
#ifdef SFTL_DEBUG
		  fprintf(stderr, "get blk %d with valid count %d\n",
		  		  sftl_free_blk, sftl_blk_valid_count[sftl_free_blk]);
#endif
		  
		  sftl_gc(sftl_free_blk, mapdir_flag);
		  if (sftl_free_count < 4)
		  {
			   fprintf(stderr, "too few free pages %d\n", sftl_free_count);
			   int err = 0;
			   int i;
			   for (i = 1; i != (sftl_blk_count >> 1); ++ i)
			   {
					if (sftl_blk_valid_count[sftl_blk_vc_idx[i]] >
						sftl_blk_valid_count[sftl_blk_vc_idx[i << 1]])
						 err = 1;
					if ((i << 1) < sftl_blk_vc_idx &&
						sftl_blk_valid_count[sftl_blk_vc_idx[i]] >
						sftl_blk_valid_count[sftl_blk_vc_idx[(i << 1) + 1]])
						 err = 1;
			   
					if (err)
					{
						 assert(0);
					}
			   }
		  }
			   
		  if (sftl_free_count != 0)
		  {
			   int i;
			   for (i = 0; i != sftl_free_count >> 1; ++ i)
			   {
					unsigned int tmp = sftl_free_arr[i];
					sftl_free_arr[i] = sftl_free_arr[sftl_free_count - i - 1];
					sftl_free_arr[sftl_free_count - i - 1] = tmp;
			   }
			   break;
		  }
	 }

	 unsigned int result = sftl_free_arr[-- sftl_free_count];
	 return result;
}

extern unsigned int stat_erase_num;

void sftl_gc(int blkno, int mapdir_flag)
{
#ifdef SFTL_DEBUG
	 fprintf(stderr, "sftl::gc called with blk = %d\n", blkno);
#endif
	 sftl_free_count = 0;
	 
	 sect_t lsns[PAGE_NUM_PER_BLK][SECT_NUM_PER_PAGE];
	 memset(lsns, 0xFF, sizeof(lsns));
	 int used;
	 int i;
	 
	 /* Fragment */
	 /* used = 0; */
	 /* for (i = 0; i != PAGE_NUM_PER_BLK; ++ i) */
	 /* { */
	 /* 	  unsigned int page = blkno * PAGE_NUM_PER_BLK + i; */
	 /* 	  if (sftl_get_valid_bitmap(page) == 1) */
	 /* 	  { */
	 /* 		   ++ used; */
	 /* 	  } */
	 /* } */

	 /* if (used > sftl_current_gc_threshold) */
	 /* { */
	 /* 	  sftl_current_gc_threshold = (used + sftl_current_gc_threshold) >> 1; */
	 /* } */

	 int valid[PAGE_NUM_PER_BLK];
	 memset(valid, 0, sizeof(valid));
	 int page_num_per_blk = PAGE_NUM_PER_BLK;
	 -- page_num_per_blk;
#if !USE_BITMAP
	 if (nand_blk[blkno].state.free == 0)
	 {
		  /* Read the inverse map */
		  sect_t _lsns[SECT_NUM_PER_PAGE];
		  int _i;
		  for  (_i = 0; _i != SECT_NUM_PER_PAGE; ++ _i)
		  {
			   _lsns[_i] = blkno;
		  }
		  nand_page_read(((blkno + 1) * PAGE_NUM_PER_BLK - 1) * 4, _lsns, 2);
	 }
#endif
	 used = 0;
	 for (i = 0; i != page_num_per_blk; ++ i)
	 {
		  unsigned int page = blkno * PAGE_NUM_PER_BLK + i;
#if USE_BITMAP
		  if (sftl_get_valid_bitmap(page) == 1)
		  {
			   valid[i] = 1;
			   nand_page_read(page * 4, lsns[i], 2);
			   ++ used;
		  }
		  else valid[i] = 0;
#else
		  if (sftl_inverse_map[page] != -1)
		  {
			   if (sftl_inverse_map[page] < -1)
			   {
					int ldn = -sftl_inverse_map[page] -2;
					if ((sftl_dir[ldn].type == SFTL_MF_DISK ||
						 sftl_dir[ldn].type == SFTL_MF_GHOST ||
						((sftl_dir[ldn].type == SFTL_MF_COMPACT ||
						  sftl_dir[ldn].type == SFTL_MF_FLAT) &&
						 sftl_dir[ldn].dirty == 0)) &&
						sftl_dir[ldn].mapping_ppn == page)
					{
						 assert(sftl_get_valid_bitmap(page) == 1);
						 
						 valid[i] = 1;
						 nand_page_read(page * 4, lsns[i], 2);
						 ++ used;
					}
					else
					{
						 assert(sftl_get_valid_bitmap(page) == 0);
						 
						 valid[i] = 0;
					}
			   }
			   else
			   {
					int ldn = sftl_inverse_map[page] / MAP_ENTRIES_PER_PAGE;
					if (sftl_dir[ldn].type == SFTL_MF_DISK)
					{
						 /* Read the map */
						 sect_t _lsns[SECT_NUM_PER_PAGE];
						 int _i;
						 for  (_i = 0; _i != SECT_NUM_PER_PAGE; ++ _i)
						 {
							  // lsns[_i] = ldn * MAP_ENTRIES_PER_PAGE * SECT_NUM_PER_PAGE + _i;
							  _lsns[_i] = -1;
						 }
						 nand_page_read(sftl_dir[ldn].mapping_ppn * 4, _lsns, 2);
						 sftl_dir[ldn].type = SFTL_MF_GHOST;
					}

					if (sftl_dir[ldn].ppn[
							 sftl_inverse_map[page] % MAP_ENTRIES_PER_PAGE] == page)
					{
						 assert(sftl_get_valid_bitmap(page) == 1);
								
						 valid[i] = 1;
						 nand_page_read(page * 4, lsns[i], 2);
						 ++ used;
					}
					else
					{
						 assert(sftl_get_valid_bitmap(page) == 0);
						 
						 valid[i] = 0;
					}
			   }
		  }
		  else
		  {
			   assert(sftl_get_valid_bitmap(page) == 0);
			   valid[i] = 0;
		  }
#endif
	 }

	 if (nand_blk[blkno].state.free == 0)
	 {
		  nand_erase(blkno);

		  if (used == 0)
			   ++ sftl_switch_merge_count;
		  else ++ sftl_partial_merge_count;
		  
		  fprintf(sftl_log_file, "OP #%d, GC #%d: %d\n",
				  sftl_operation_count, ++ sftl_gc_count, used);
	 }
	 nand_blk[blkno].state.free = 0;
	 
	 used = 0;
	 for (i = 0; i != page_num_per_blk; ++ i)
	 {
		  unsigned int page = blkno * PAGE_NUM_PER_BLK + i;
		  if (valid[i])
		  {
#ifdef SFTL_DEBUG
			   fprintf(stderr, "write\n");
#endif
			   nand_page_write(page * 4, lsns[i], 1, mapdir_flag);
			   ++used;
		  }
		  else
		  {
			   sftl_free_arr[sftl_free_count ++] = page;
		  }

#if !USE_BITMAP
		  if (sftl_inverse_map[page] >= 0)
		  {
			   int ldn = sftl_inverse_map[page] / MAP_ENTRIES_PER_PAGE;
			   if (sftl_dir[ldn].type == SFTL_MF_GHOST)
					sftl_dir[ldn].type = SFTL_MF_DISK;
		  }
#endif
	 }
}

struct ftl_operation sftl_op = 
{
init: sftl_init,
read: sftl_read,
write: sftl_write,
end: sftl_end
};

struct ftl_operation *sftl_setup()
{
	 return &sftl_op;
}
